重复的DNA序列

[编程题]重复的DNA序列

热度指数：2447 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。

请你实现一个函数找出所有的目标子串，目标子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的子串（允许两个子串有重合的部分，如下面的示例2所示）。

（注：返回的所有目标子串的顺序必须与原DNA序列的顺序一致，如下面的示例1所示）

数据范围：DNA序列长度满足 $1 \le n \le 10^5 \$ ，保证序列中只出现 'A' , 'C' , 'G' , 'T'。

示例1

输入

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出

["AAAAACCCCC","CCCCCAAAAA"]

说明

"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 
不能返回["CCCCCAAAAA","AAAAACCCCC"]，因为在原DNA序列中，"AAAAACCCCC"要比"CCCCCAAAAA"先出现。

示例2

输入

"AAAAAAAAAAA"

输出

["AAAAAAAAAA"]

算法知识视频讲解

查看答案及解析

Python 3

danspace

class Solution:
    def repeatedDNA(self , DNA: str) -> List[str]:
        # write code here
        res = []
        d = {}
        for i in range(len(DNA)-9):
            sub = DNA[i:i+10]
            d[sub] = d.get(sub,0)+1
        for sub in d:
            if d[sub] > 1:
                res.append(sub)
        return res

发表于 2022-04-27 08:53:51 回复(0)